//给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 
//
// 说明： 
//
// 
// 拆分时可以重复使用字典中的单词。 
// 你可以假设字典中没有重复的单词。 
// 
//
// 示例 1： 
//
// 输入: s = "leetcode", wordDict = ["leet", "code"]
//输出: true
//解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
// 
//
// 示例 2： 
//
// 输入: s = "applepenapple", wordDict = ["apple", "pen"]
//输出: true
//解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
//     注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出: false
// 
// Related Topics 动态规划 
// 👍 654 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：单词拆分
public class P139WordBreak {

    /**
     * 官方题解，动态规划  当前的dp[i]是前面的dp[k]有为ture的，然后subString(k,i) 还在list中的
     *
     * 执行用时： 14 ms , 在所有 Java 提交中击败了 11.72% 的用户 内存消耗： 39.9 MB , 在所有 Java 提交中击败了 41.77% 的用户
     */

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            // dp[i] 前i个字符串有
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;

            for (int i = 1; i <= s.length(); i++) {
                for (int k = 0; k < i; k++) {
                    if (dp[k] && wordDict.contains(s.substring(k, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("cats");
        list.add("and");
        Solution solution = new P139WordBreak().new Solution();
        System.out.println(solution.wordBreak("catsandog",list));
        // TO TEST
    }

}